package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

/**
 * 把数组排成最小的数
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：474057
 * 本题知识点： 数组
 *  算法知识视频讲解
 * 题目描述
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 * 示例1
 * 输入
 * 复制
 * [3,32,321]
 * 返回值
 * 复制
 * "321323"
 */
public class PrintMinNumber {

    @Test
    public void test() {
        System.out.println(PrintMinNumber(new int[]{3, 32, 321}));
    }

    // 思路：按照其他题解，要合理的给numbers排序的话，首先要有合理的排序规则，
    // 即两数拼接时较小的情况的次序作为他们之间的大小顺序，
    // 下面是我对归并排序的变式来对这个思路进行优化。
    public String PrintMinNumber(int[] numbers) {

        int[] temp = new int[numbers.length];

        diffSort(numbers, 0, numbers.length - 1, temp);

        StringBuffer buffer = new StringBuffer();

        for (int i = 0; i < numbers.length; i++) {
            buffer.append(numbers[i]);
        }

        return buffer.toString();
    }

    private void diffSort(int[] numbers, int left, int right, int[] temp) {

        int mid = (left + right) / 2;

        if (left < right) {
            diffSort(numbers, left, mid, temp);
            diffSort(numbers, mid + 1, right, temp);
            diffMergeSort(numbers, left, mid, right, temp);
        }
    }

    private void diffMergeSort(int[] numbers, int left, int mid, int right, int[] temp) {

        int i = left;
        int j = mid + 1;
        int index = left;

        while (i <= mid && j <= right) {
            String a = String.valueOf(numbers[i]);
            String b = String.valueOf(numbers[j]);
            if (Integer.parseInt(a + b) < Integer.parseInt(b + a)) {
                temp[index++] = numbers[i++];
            } else {
                temp[index++] = numbers[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = numbers[i++];
        }

        while (j <= right) {
            temp[index++] = numbers[j++];
        }

        while (left <= right) {
            numbers[left] = temp[left++];
        }
    }

// 思路：补充数位然后归并排序然后再字符串拼接：
//    public String PrintMinNumber(int[] numbers) {
//
//        int max = 0; // 最大位数
//
//        // 找出最大位数
//        for (int i = 0; i < numbers.length; i++) {
//            int temp = numbers[i];
//            int length = 0;
//            while (temp != 0) {
//                length++;
//                temp /= 10;
//            }
//            if (length > max) {
//                max = length;
//            }
//        }
//
//        int[] clone = numbers.clone();
//
//        // 补齐数位
//        for (int i = 0; i < numbers.length; i++) {
//            while (clone[i] / (int) Math.pow(10, max - 1) == 0) {
//                clone[i] = clone[i] * 10 + clone[i] % 10;
//            }
//        }
//
//        // 构建二维数组
//        ArrayList<int[]> list = new ArrayList<>();
//
//        for (int i = 0; i < clone.length; i++) {
//            list.add(new int[]{clone[i], numbers[i]});
//        }
//
//        int[] temp = new int[clone.length];
//
//        sort(clone, 0, clone.length - 1, temp);
//
//        StringBuffer buffer = new StringBuffer();
//
//        // 对应clone找numbers
//        for (int i = 0; i < clone.length; i++) {
//            for (int j = 0; j < list.size(); j++) {
//                if (list.get(j)[0] == clone[i]) {
//                    buffer.append(list.get(j)[1]);
//                    list.remove(list.get(j));
//                }
//            }
//        }
//
//        return buffer.toString();
//    }
//
//    //归并排序的实现
//    private void sort(int[] arr, int left, int right, int[] temp) {
//
//        int mid = (left + right) / 2;
//
//        if (left < right) { //记住：这里是if，别再写while了
//            sort(arr, left, mid, temp);
//            sort(arr, mid + 1, right, temp);
//            mergeSort(arr, left, mid, right, temp);
//        }
//    }
//
//    private void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
//
//        int i = left;
//        int j = mid + 1;
//        int index = left;
//
//        while (i <= mid && j <= right) {
//            if (arr[i] < arr[j]) {
//                temp[index++] = arr[i++];
//            } else {
//                temp[index++] = arr[j++];
//            }
//        }
//
//        while (i <= mid) {
//            temp[index++] = arr[i++];
//        }
//
//        while (j <= right) {
//            temp[index++] = arr[j++];
//        }
//
//        while (left <= right) {
//            arr[left] = temp[left++];
//        }
//    }
}
